import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //动态数组
        List<Integer> ret = new ArrayList<>();
        //用 hash1 来记录 pp 里面的字符出现次数
        int[] hash1 = new int[26];
        for (char c:p) {
            hash1[c - 'a']++;
        }
        //滑动窗口的左右界限,count记录有效字符
        //开始进行入窗口和出窗口操作
        int[] hash2 = new int[26];
        for (int right = 0,left = 0,count =0; right < s.length; right++) {
            //挨个取出s数组中的字符
            char in = s[right];
            //未达到边界，入窗口
                if (++hash2[in - 'a'] <= hash1[in - 'a'])count++;
                //出窗口
            if (right - left + 1 > p.length){
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            if (count == p.length) ret.add(left);
        }
        return ret;
    }

    public static void main(String[] args) {
        String ss = "cbaebabacd";
        String pp = "abc";
        Solution s = new Solution();
        List<Integer> list = s.findAnagrams(ss,pp);
        System.out.println(list.toString());
    }
}
